Python Implementation of Dijkstra

To implement Dijkstra's algorithm efficiently, we use a Min-Heap structure, provided by Python's built-in `heapq` module, to manage the Priority Queue.

The core mechanism maps directly to the conceptual steps: initialization, loop, extraction, and relaxation.
We initialize the distances dictionary with $\infty$ for all nodes and $0$ for the starting node.
The Priority Queue (PQ) stores tuples of `(distance, node)` to ensure the node with the smallest distance is always popped first.
A common optimization checks if the extracted distance is greater than the currently recorded distance, implicitly handling stale entries in the PQ.
The relaxation step updates a neighbor's distance only if a shorter path is found through the current node.
The overall time complexity is typically $O(V \log V + E \log V)$ when using a binary heap.

1import heapq 2 3def dijkstra(graph, start): 4 # 1. Initialization 5 distances = {node: float('inf') for node in graph} 6 distances[start] = 0 7 pq = [(0, start)] # (distance, node) 8 9 # 2. Main Loop 10 while pq: 11 # 3. Pop Min 12 current_distance, current_node = heapq.heappop(pq) 13 14 # 4. Visited Check (Optimization) 15 if current_distance > distances[current_node]: 16 continue # This is a stale, worse path. 17 18 # 5. Relax Neighbors 19 for neighbor, weight in graph[current_node].items(): 20 new_distance = current_distance + weight 21 22 if new_distance < distances[neighbor]: 23 # Found a shorter path 24 distances[neighbor] = new_distance 25 heapq.heappush(pq, (new_distance, neighbor)) 26 27 return distances